package com.xyhuo.leetcode.december;

/**
 * 跳跃游戏Ⅱ
 * https://leetcode.cn/problems/jump-game-ii/
 *
 * @time 2023/12/18
 */
public class Jump {

//    public static void main(String[] args) {
//        Jump jump = new Jump();
//        int[] nums = {2, 3, 1, 1, 4};
//        int ans = jump.jump(nums);
//        System.out.println(ans);
//    }

    public int jump(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        for (int i = 1; i < len; i++) {
            int j = 0;
            Integer tmp = null;
            while (true) {
                if (i - 1 - j < 0) {
                    break;
                }
                if (nums[i - 1 - j] > j) {
                    tmp = tmp == null ? dp[i - 1 - j] + 1 : Math.min(dp[i - 1 - j] + 1, tmp);
                }
                j++;
            }
            dp[i] = tmp;
        }
        return dp[len - 1];
    }
}
